how come this question is downgraded as a medium question suddenly?

Using an OrderedDict / LinkedHashMap to solve this problem in an interview setting is like using [::-1] / .reverse() to solve how to reverse a string, yeah you got it right but is that what the interviewer is looking for?

I'd find a much better explanation and solution from the discussion section.

@gchggy
Java version: https://leetcode.com/problems/lru-cache/discuss/45911/Java-Hashtable-%2B-Double-linked-list-(with-a-touch-of-pseudo-nodes)
Python version: https://leetcode.com/problems/lru-cache/discuss/45926/Python-Dict-%2B-Double-LinkedList

leetcode solution and discussions complement each other

it would be nice if you posted a link to whatever you found better in the discuss section.

True, but in this case, someone copy pasted the same solution in discussion.

It's always true somehow

I really like the dummy head & tail technique. Much more simple implementation with those in place and really minimal extra memory overhead. I just spent an hour catching all the edge cases without them! I'm puzzled why my solution is slower than most - I presume most solutions are cheating and using an LinkedHashMap. I also suspect the performance numbers are based on unrealistically small sample sets.

Java Solution. Not a huge fan of the code proposed for solution #2. Here is a more straight forward code (same approach, just cleaner code).

class Node {
  int value;
  int key;
  Node prev;
  Node next;
  public Node() {}

  public Node(int key, int value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class DoublyLinkedList {
  Node head;
  Node tail;
  
  public DoublyLinkedList() {
    head = new Node();
    tail = new Node();
    this.head.next = this.tail;
    this.tail.prev = head;
  }
  
  public void insertHead(Node n) {
    n.prev = head;
    n.next = head.next;
    head.next.prev = n;
    head.next = n;    
  }
  
  public void remove(Node n) {
    n.prev.next = n.next;
    n.next.prev = n.prev;
  }
  
  public int removeTail() {
    Node n = tail.prev;
    int key = n.key;
    remove(n);
    
    return key;
  }
}

class LRUCache {
  Map<Integer,Node> cache;
  DoublyLinkedList list;
  int capacity;
  
  public LRUCache(int capacity) {
    this.capacity = capacity;
    this.cache = new HashMap<>();
    this.list = new DoublyLinkedList();
  }
  
  public int get(int key) {
    if (!cache.containsKey(key)) 
        return -1;    
    update(key, cache.get(key));
      
    return cache.get(key).value;
  }
  
  public void put(int key, int value) {
    Node n = new Node(key, value);
      
    if (cache.containsKey(key))
      list.remove(cache.get(key));
    else if (cache.size() >= capacity) {
        int k = list.removeTail();
        cache.remove(k);
    }
        
    list.insertHead(n);
    cache.put(key, n);
  }
  
  private void update(int key, Node n) {    
    list.remove(n);
    list.insertHead(n);
    cache.put(key, n);
  }
}

@KingXun good question! The key in DLinkedNode would help us to remove the node itself from the cache at the moment the node becomes stale and is removed along with the invocation of the function popTail. We need to keep the key along with the node itself, because when the node is removed, we are not blessed with the key from the caller of LRU cache.

tried everything I could, stack, de-que, priority queue, etc. I just never thought about using the f..king linked list! This drives me crazy.

@wolfhound115 Can't delete a random node in deque except for the first or last. DLL can. That's why a vanilla Linked List won't work as well.

wait but a deque is effectively a doubly linked list right? (at least in the python implementation of it)

It's crazy. Agree.

why remove oldest? what if a cache is frequently used and the eldest the same time?

Does the interviewer really expects you to write this much code in just 30 mins?

I do not understand how this could possibly be implemented within 30 minutes without having prior knowledge of the question, especially if it is a whiteboard interview.

Can we assume a doubly linked list implementation is provided, implement only get and put, using assumed functions for doubly linked list? That would seem reasonable, otherwise the volume of this code just seems too much, even more so if you have to handle edge cases because you didn’t use dummy head and tail variables.